package utils;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/1 9:02
 * @description:
 */
/*
红黑树的五点核心性质是判断其合法性的关键，具体如下：

1. **性质1：节点颜色要么是红色，要么是黑色**
   树中每个节点必须明确被标记为红色（RED）或黑色（BLACK），不存在其他颜色。

2. **性质2：根节点必须是黑色**
   红黑树的根节点颜色固定为黑色，这是为了保证树的稳定性。

3. **性质3：所有叶子节点（NIL节点）必须是黑色**
   红黑树中，所有叶子节点都是虚构的“NIL节点”（不存储数据的哨兵节点），且这些节点必须为黑色。

4. **性质4：如果一个节点是红色，则它的两个子节点必须是黑色**
   红色节点不能有红色子节点（即不存在“红-红”直接相连的父子关系），这是为了避免树的倾斜。

5. **性质5：从任意节点到其所有叶子节点的路径中，包含的黑色节点数量相同**
   这条性质称为“黑平衡”，确保了红黑树的最长路径不超过最短路径的2倍，从而保证查询效率为O(log n)。


在你提供的示例中，输出“违反性质5”，说明从节点5到叶子的黑色节点数量，与从根节点（10）到叶子的黑色节点数量不一致，破坏了黑平衡。这通常是插入/删除操作后，旋转或变色逻辑有误导致的。
 */

import datastructure.redblacktree.RedBlackTree;

import java.util.Stack;

public class RedBlackTreeValidator<T extends Comparable<T>> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private final RedBlackTree<T>.Node nil;

    public RedBlackTreeValidator(RedBlackTree<T> tree) {
        this.nil = tree.nil;
    }

    /**
     * 验证整棵树是否为合法红黑树
     */
    public boolean isValidRedBlackTree(RedBlackTree<T>.Node root) {
// 性质 2：根节点必须是黑色（空树除外）
        if (root != nil && root.color != BLACK) {
            System.out.println("违反性质 2：根节点不是黑色");
            return false;
        }
// 性质 3：所有叶子节点（NIL）必须是黑色
        if (nil.color != BLACK) {
            System.out.println("违反性质 3：NIL 叶子节点不是黑色");
            return false;
        }
// 检查其他性质（1、4、5）
        return checkNodesAndPaths(root);
    }

    /**
     * 遍历所有节点，检查性质 1、4，并验证性质 5（每个节点的左右子树黑高度相等）
     */
    private boolean checkNodesAndPaths(RedBlackTree<T>.Node root) {
        if (root == nil) return true;
        Stack<RedBlackTree<T>.Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            RedBlackTree<T>.Node node = stack.pop();
// 性质 1：节点颜色必须是红或黑
            if (node.color != RED && node.color != BLACK) {
                System.out.println("违反性质 1：节点" + node.key + "颜色不合法");
                return false;
            }
// 性质 4：红色节点的子节点必须是黑色
            if (node.color == RED) {
                if (node.left.color != BLACK) {
                    System.out.println("违反性质 4：红色节点" + node.key + "的左子节点不是黑色");
                    return false;
                }
                if (node.right.color != BLACK) {
                    System.out.println("违反性质 4：红色节点" + node.key + "的右子节点不是黑色");
                    return false;
                }
            }
// 跳过叶子节点（NIL）的子节点检查
            if (node == nil) continue;
// 性质 5：当前节点的左右子树黑高度必须相等
            int leftBlackHeight = calculateBlackHeight(node.left);
            int rightBlackHeight = calculateBlackHeight(node.right);
            if (leftBlackHeight != rightBlackHeight) {
                System.out.println("违反性质 5：节点" + node.key + "的左右子树黑高度不一致（左：" + leftBlackHeight + "，右：" + rightBlackHeight + "）");
                return false;
            }
// 继续遍历子节点
            stack.push(node.right);
            stack.push(node.left);
        }
        return true;
    }

    /**
     * 计算从当前节点到叶子节点的黑高度（黑色节点数量）
     */
    private int calculateBlackHeight(RedBlackTree<T>.Node node) {
// 叶子节点（NIL）的黑高度为 1（自身是黑色）
        if (node == nil) {
            return 1;
        }
// 递归计算左右子树的黑高度（已在 checkNodesAndPaths 中确保左右相等）
        int childBlackHeight = calculateBlackHeight(node.left);
        if (childBlackHeight == -1) return -1; // 子树不满足性质 5
// 当前节点为黑色时，黑高度 + 1
        return (node.color == BLACK ? 1 : 0) + childBlackHeight;
    }

    // 测试方法
    public static void main(String[] args) {
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        int[] values = {10, 20, 5, 15, 30};
        for (int val : values) {
            tree.insert(val);
        }
        tree.printTree();

        RedBlackTreeValidator<Integer> validator = new RedBlackTreeValidator<>(tree);
        boolean isValid = validator.isValidRedBlackTree(tree.root);
        System.out.println("红黑树是否合法：" + isValid); // 现在会输出 true
    }
}